﻿#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"


//交换元素
void swap(int* p1, int* p2) {
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

//堆排序
void xiangXiaTiaoZheng(int* arr, int pr, int k) {//向下调整
	int ch = pr * 2 + 1;
	while (ch < k) {
		if (ch + 1 < k && arr[ch + 1] > arr[ch]) ch++;
		if (arr[ch] > arr[pr]) {
			swap(arr + ch, arr + pr);
			pr = ch;
			ch = pr * 2 + 1;
		}
		else return;
	}
}
void jianDui(int* arr, int k)//建堆
{
	for (int i = (k - 2) / 2; i >= 0; i--) {
		xiangXiaTiaoZheng(arr, i, k);
	}
}
void HeapSort(int* a, int n)
{
	jianDui(a, n);
	int end = n - 1;
	while (end > 0) {
		swap(a, a + end);
		xiangXiaTiaoZheng(a, 0, end);
		end--;
	}
}

//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int y = 0; y < n - 1; y++)
	{
		int flag = 1;
		int len = n - y;
		for (int i = 0; i < len - 1; i++)
		{
			if (a[i] > a[i + 1])
			{
				swap(a + i + 1, a + i);
				flag = 0;
			}
		}
		if (flag) return;
	}
}

//希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		int i = 0;
		while (i < gap)
		{
			int y = i;
			while (1)
			{
				if (y >= n || y + gap >= n)
					break;
				if (a[y + gap] < a[y]) {
					int x = y;
					int tmp = a[y + gap];
					while (x >= 0 && tmp < a[x])
					{
						a[x + gap] = a[x];
						x -= gap;
					}
					a[x + gap] = tmp;
				}
				y += gap;
			}
			i++;
		}
	}
}

//选择排序
void SelectSort1(int* a, int n)//取小交换
{
	for (int y = 0; y < n - 1; y++) {
		int i = y;
		int tmp = y + 1;
		for (; tmp < n; tmp++)
		{
			if (a[tmp] < a[i])
				i = tmp;
		}
		swap(a + i, a + y);
	}
}
void SelectSort(int* a, int n)//优化，取大小交换
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int min = begin;
		int max = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[min])
				min = i;
			else if (a[i] > a[max])
				max = i;
		}
		swap(a + begin, a + min);
		if (begin == max)
			max = min;
		swap(a + end, a + max);
		begin++;
		end--;
	}
}

//快速排序
int QuZhong(int* arr, int first, int last)//优化，三数取中
{
	int z = (first + last) / 2;
	int a = arr[first];
	int b = arr[z];
	int c = arr[last];
	if (b > c)
	{
		if (c > a)
			return last;
		else
		{
			if (a < b)
				return first;
			else
				return z;
		}
	}
	else
	{
		if (b > a)
			return z;
		else
		{
			if (a < c)
				return first;
			else
				return last;
		}
	}
}
void QuickSort(int* a, int begin, int end)//hoare版本
{
	if (begin >= end)
		return;
	if ((end - begin + 1) < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	int z = QuZhong(a, begin, end);
	swap(a + begin, a + z);
	int tmp = a[begin];
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[right] >= tmp)
		{
			right--;
		}
		while (left < right && a[left] <= tmp)
		{
			left++;
		}
		swap(a + left, a + right);
	}
	swap(a + begin, a + left);
	QuickSort(a, begin, left - 1);
	QuickSort(a, left + 1, end);
}
void QuickSort1(int* a, int begin, int end)//挖坑法版本
{
	if (begin >= end)
		return;
	if ((end - begin + 1) < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	int z = QuZhong(a, begin, end);
	swap(a + begin, a + z);
	int tmp = a[begin];
	int tmpi = begin;
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && a[right] >= tmp)
		{
			right--;
		}
		if (left < right)
		{
			swap(a + tmpi, a + right);
			tmpi = right;
			left++;
		}
		while (left < right && a[left] <= tmp)
		{
			left++;
		}
		if (left < right)
		{
			swap(a + tmpi, a + left);
			tmpi = left;
			right--;
		}
	}
	QuickSort1(a, begin, left - 1);
	QuickSort1(a, left + 1, end);
}
void QuickSort2(int* a, int begin, int end)//双指针版本
{
	if (begin >= end)
		return;
	if ((end - begin + 1) < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	int z = QuZhong(a, begin, end);
	swap(a + begin, a + z);
	int prev = begin;
	int cut = begin + 1;
	int tmp = a[begin];
	while (cut <= end)
	{
		while (cut <= end && a[cut] <= tmp)
		{
			prev++;
			cut++;
		}
		while (cut <= end && a[cut] > tmp)
		{
			cut++;
		}
		if (cut <= end)
		{
			prev++;
			swap(a + prev, a + cut);
		}
	}
	swap(a + begin, a + prev);
	QuickSort2(a, begin, prev - 1);
	QuickSort2(a, prev + 1, end);
}

void QuickSortByThree_way(int* a, int begin, int end)//三路划分
{
	if (begin >= end)
		return;
	if ((end - begin + 1) < 10)
	{
		InsertSort(a + begin, end - begin + 1);
		return;
	}
	int z = QuZhong(a, begin, end);
	swap(a + begin, a + z);
	int left = begin;
	int cut = left + 1;
	int right = end;
	while (cut<=right)
	{
		if (a[cut] == a[left]) {
			cut++;
		}
		else if (a[cut] > a[left]) {
			swap(a + cut, a + right);
			right--;
		}
		else {
			swap(a + left, a + cut);
			left++;
			cut++;
		}
	}
	
	QuickSortByThree_way(a, begin, left-1);
	QuickSortByThree_way(a, right+1, end);
}

void QuickSortNonR(int* a, int begin, int end) 	//非递归版本
{
	Stack sk;
	StackInit(&sk);
	StackPush(&sk, end);
	StackPush(&sk, begin);
	while (!StackEmpty(&sk))
	{
		int left = StackTop(&sk);
		int right = StackTop(&sk);
		int rembegin = left;
		int remend = right;
		int tmp = a[left];

		while (left < right)
		{
			while (left < right && a[right] >= tmp)
			{
				right--;
			}
			while (left < right && a[left] <= tmp)
			{
				left++;
			}
			swap(a + left, a + right);
		}
		swap(a + rembegin, a + left);
		if (left + 1 < remend) {
			StackPush(&sk, remend);
			StackPush(&sk, left + 1);
		}
		if (rembegin < left - 1) {
			StackPush(&sk, left - 1);
			StackPush(&sk, rembegin);
		}
	}
	StackDestroy(&sk);
}

void MergeSort(int* a, int begin, int end)//归并排序
{
	int n = end - begin + 1;
	if (n < 2) return;
	int min = begin + n / 2;
	MergeSort(a, begin, min - 1);
	MergeSort(a, min, end);
	int* arr = (int*)malloc(sizeof(int) * n);
	int left = begin;
	int right = min;
	int i = 0;
	while (left < min && right <= end)
	{
		if (a[left] < a[right])
		{
			arr[i++] = a[left++];
		}
		else
		{
			arr[i++] = a[right++];
		}
	}
	if (left == min) {
		while (right <= end) {
			arr[i++] = a[right++];
		}
	}
	else
	{
		while (left < min) {
			arr[i++] = a[left++];
	 	}
	}
	i = 0;
	for (int y = begin; y <= end; y++)
	{
		a[y] = arr[i++];
	}
	free(arr);
}

void MergeSortNonR(int* a, int begin, int end)//非递归版本
{
	int gap = 1;
	int n = end - begin + 1;
	int* arr = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int y = 0; y < n; y += gap * 2)
		{
			int left = y;
			int right = y + gap;
			if (right >= n) {
				for (int z = left; z < n; z++)
				{
					arr[z] = a[z];
				}
				break;
			}
			int i = y;
			int end1 = y + gap;
			int end2 = right + gap;
			if (end2 >= n)
				end2 = n;
			while (left < end1 && right < end2)
			{
				if (a[left] < a[right])
				{
					arr[i++] = a[left++];
				}
				else
				{
					arr[i++] = a[right++];
				}
			}
			if (left == end1) {
				while (right < end2) {
					arr[i++] = a[right++];
				}
			}
			else
			{
				while (left < end1) {
					arr[i++] = a[left++];
				}
			}
		}
		for (int z = 0; z < n; z++)
		{
			a[z] = arr[z];
		}
		gap *= 2;
	}
	free(arr);
}

//计数排序
void CountSort(int* a, int n)
{
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		else if (a[i] > max)
			max = a[i];
	}
	int countN = max - min + 1;
	int* arr = (int*)calloc(countN, sizeof(int));
	for (int i = 0; i < n; i++)
	{
		arr[a[i] - min]++;
	}
	int y = 0;
	for (int i = 0; i < countN&&y<n; i++)
	{
		int sz = arr[i];
		while (sz--)
		{
			a[y++] = i + min;
		}
	}
}